import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class CentsCombo {

	public static void main(String[] args) {
		CentsCombo cc = new CentsCombo();
		List<Map<Integer, Integer>> list = cc.getCombo2(25, 25);
		for (Map<Integer, Integer> map : list) {
			System.out.println(map.toString());
		}
		// System.out.println(cc.getCombo2(25, 25));
	}

	public List<Map<Integer, Integer>> getCombo2(int n, int d) {
		int next_d = 0;
		switch (d) {
		case 25:
			next_d = 10;
			break;
		case 10:
			next_d = 5;
			break;
		case 5:
			next_d = 1;
			break;
		case 1:
			List<Map<Integer, Integer>> list = new ArrayList<Map<Integer, Integer>>();
			Map<Integer, Integer> map = new HashMap<Integer, Integer>();
			map.put(1, n);
			list.add(map);
			return list;
		}

		List<Map<Integer, Integer>> list = new ArrayList<Map<Integer, Integer>>();
		for (int i = 0; i * d <= n; ++i) {
			List<Map<Integer, Integer>> sublist = getCombo2(n - i * d, next_d);
			for (Map<Integer, Integer> map : sublist)
				map.put(d, i);
			list.addAll(sublist);
		}
		return list;
	}

	public Set<Map<Integer, Integer>> getCombo(int n) {
		if (n <= 0)
			return null;

		if (n == 1) {
			Set<Map<Integer, Integer>> list = new HashSet<Map<Integer, Integer>>();
			Map<Integer, Integer> map = new HashMap<Integer, Integer>();
			map.put(1, 1);
			list.add(map);
			return list;
		}

		if (n == 5) {
			Set<Map<Integer, Integer>> list = getCombo(4);
			for (Map<Integer, Integer> m : list) {
				m.put(1, m.get(1) + 1);
			}
			Map<Integer, Integer> map = new HashMap<Integer, Integer>();
			map.put(5, 1);
			list.add(map);
			return list;
		}

		if (n == 10) {
			Set<Map<Integer, Integer>> list = getCombo(9);
			for (Map<Integer, Integer> m : list) {
				m.put(1, m.get(1) + 1);
			}
			Map<Integer, Integer> map = new HashMap<Integer, Integer>();
			map.put(10, 1);
			list.add(map);
			map = new HashMap<Integer, Integer>();
			map.put(5, 2);
			list.add(map);
			return list;
		}

		if (n == 25) {
			Set<Map<Integer, Integer>> list = getCombo(24);
			for (Map<Integer, Integer> m : list) {
				m.put(1, m.get(1) + 1);
			}
			Map<Integer, Integer> map = new HashMap<Integer, Integer>();
			map.put(25, 1);
			list.add(map);
			return list;
		}

		Set<Map<Integer, Integer>> list = new HashSet<Map<Integer, Integer>>();
		for (int i : new int[] { 1, 5, 10, 25 }) {
			Set<Map<Integer, Integer>> li = getCombo(n - i);
			if (li != null) {
				for (Map<Integer, Integer> m : li) {
					if (m.containsKey(i))
						m.put(i, m.get(i) + 1);
					else
						m.put(i, 1);
				}
				list.addAll(li);
			}
		}

		return list;
	}

}
